package com.test.java;

import java.util.Scanner;

/**
 * 现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法
 * =============================================================
 * Version          Author          Date            Description
 * 1.0              白建         2017/12/29             创建
 * =============================================================
 */
public class Java_26
{

    public static void main(String[] args)
    {

        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] input = new int[N];
        int[] midStep = new int[N];

        scanner.nextLine();
        for (int i = 0; i < 2 * N; i++)
        {
            if (i < N)
            {
                input[i] = scanner.nextInt();
            }
            else
            {
                midStep[i - N] = scanner.nextInt();
            }
        }
        int[] inputClone = new int[N];
        for (int i = 0; i < N; i++)
        {
            inputClone[i] = input[i];
        }
        insertionSort(input, midStep);
        mergeSort(inputClone, midStep, 0, input.length - 1);
    }

    private static void insertionSort(int[] input, int[] midStep)
    {

        int length = input.length;
        int temp;
        boolean flag = false;
        for (int i = 1; i < length; i++)
        {
            for (int j = i; j > 0; j--)
            {
                if (input[j] < input[j - 1])
                {
                    temp = input[j - 1];
                    input[j - 1] = input[j];
                    input[j] = temp;
                }
            }
            if (flag)
            {
                System.out.println("Insertion Sort");
                for (int k = 0; k < length - 1; k++)
                {
                    System.out.print(input[k] + " ");
                }
                System.out.print(input[length - 1]);
                System.exit(-1);
            }
            if (match(input, midStep))
            {
                flag = true;
            }
        }
    }

    private static boolean mergeSort(int[] input, int[] midStep, int low, int high)
    {

        if (low >= high)
        {
            return false;
        }
        //todo:归并排序
        int mid = (high + low) / 2;
        if (mergeSort(input, midStep, low, mid))
        {
            System.out.println("Merge Sort");
            for (int k = 0; k < input.length - 1; k++)
            {
                System.out.print(input[k] + " ");
            }
            System.out.print(input[input.length - 1]);
            System.exit(-1);
        }
        if (mergeSort(input, midStep, mid + 1, high))
        {
            System.out.println("Merge Sort");
            for (int k = 0; k < input.length - 1; k++)
            {
                System.out.print(input[k] + " ");
            }
            System.out.print(input[input.length - 1]);
            System.exit(-1);
        }
        return merge(input, midStep, low, mid, high);
    }

    private static boolean merge(int[] input, int[] midStep, int low, int mid, int high)
    {

        int i = low, j = mid + 1, k = 0;
        int length = high - low + 1;
        int[] tempList = new int[length];
        while (i <= mid && j <= high)
        {
            if (input[i] < input[j])
            {
                tempList[k] = input[i];
                i++;
                k++;
            }
            else
            {
                tempList[k] = input[j];
                j++;
                k++;
            }
        }
        for (; j <= high; j++, k++)
        {
            tempList[k] = input[j];
        }
        for (; i <= mid; i++, k++)
        {
            tempList[k] = input[i];
        }

        for (k = 0; k < high - low + 1; k++)
        {
            input[k + low] = tempList[k];
        }
        return match(input, midStep);
    }

    private static boolean match(int[] input, int[] midStep)
    {

        for (int i = 0; i < input.length; i++)
        {
            if (input[i] != midStep[i])
            {
                return false;
            }
        }
        return true;
    }
}
